The "Fairness" of Sorting: What is Stability? A Case Study of Insertion Sort

The "stability" of sorting refers to whether the relative order of equal elements remains unchanged after sorting; if it does, the sort is stable. Insertion sort achieves stability through its unique insertion logic. The core of insertion sort is to insert unordered elements one by one into the ordered portion. When inserting equal elements, no swap occurs; instead, the element is directly inserted after the equal elements. For example, in the array [3, 1, 3, 2], when processing the second 3, since it is equal to the 3 at the end of the ordered portion, it is directly inserted after it. The final sorted result is [1, 2, 3, 3], and the relative order of the original two 3s remains unchanged. The key to stability lies in preserving the original order of equal elements. This is crucial in practical scenarios such as grade ranking and order processing, where fair sorting according to the original order is required. Due to its logic of "no swap for equal elements, insert later", insertion sort naturally guarantees stability, ensuring that duplicate elements always remain in their original order and reflecting the "fairness" of the sort.